#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
using namespace std;

struct Interval {
	int start;
	int end;
	Interval() : start(0), end(0) {}
	Interval(int s, int e) : start(s), end(e) {}
};
class Solution {
public:
	vector<Interval> insert(vector<Interval> &intervals, Interval ni) {
		// Start typing your C/C++ solution below
		// DO NOT write int main() function
		int interIdx = -1, afterIdx = -1;
		for(size_t i=0;i<intervals.size();i++)
		{
			int rc = testIntersect(ni,intervals[i]);
			if(rc > 0)
			{
				continue;
			}
			else if(!rc)
			{
				if(-1 == interIdx)
					interIdx = i;
				else
					continue;
			}
			else
			{
				//rc<0
				afterIdx = i;
				break;
			}

		}

		if(interIdx != -1)
		{
			if(afterIdx == -1)
			{
				afterIdx = intervals.size();
			}
			for(int i=interIdx;i<afterIdx;i++)
			{
				merge(ni,intervals[i]);
			}

			intervals.erase(intervals.begin() + interIdx,intervals.begin() + afterIdx);
			if(intervals.size() <= interIdx)
			{
				intervals.push_back(ni);
			}
			else
				intervals.insert(intervals.begin() + interIdx,ni);
		}
		else
		{
			if(afterIdx == -1)
				intervals.push_back(ni);
			else
				intervals.insert(intervals.begin()+afterIdx,ni);
		}

		return intervals;        
	}
private:
	int testIntersect(const Interval& s1, const Interval& s2)
	{
		if(s1.end < s2.start)
			return -1;
		else if(s1.start > s2.end)
			return 1;
		else
			return 0;
	}

	void merge(Interval& ni, const Interval& s2)
	{
		ni.start = min(ni.start,s2.start);
		ni.end = max(ni.end,s2.end);
	}
};
#endif